/**
 * @author ZhiWen Ren
 * @version 1.0
 * @description: LeetCode-64-最小路径和
 * @date 2025/8/22 14:54
 */
public class Solution64 {
    /*public static int minPathSum(int[][] grid) {
        int ans = 0, m = grid.length, n = grid[0].length;
        int[] path = new int[n];

        for (int i = m - 1; i >= 0; i--) {
            for (int j = n - 1; j >= 0; j--) {
                if (j >= n - 1) {
                    path[j] += grid[i][j];
                    continue;
                }
                int low = Integer.MAX_VALUE;
                if (i < m - 1) {
                    low = path[j];
                }
                path[j] = grid[i][j] + Math.min(low, path[j + 1]);
            }
        }

        return path[0];
    }*/
    public static int minPathSum(int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;
        int[] paths = new int[n];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (i == 0 && j > 0) {
                    paths[j] = paths[j - 1] + grid[i][j];
                } else if (j == 0) {
                    paths[j] += grid[i][j];
                } else {
                    paths[j] = Math.min(paths[j], paths[j - 1]) + grid[i][j];
                }
            }
        }
        return paths[n - 1];
    }

    public static void main(String[] args) {
        System.out.println(minPathSum(new int[][]{{1, 3, 1}, {1, 5, 1}, {4, 2, 1}}));
    }
}
